Search for: All records

Abstract We introduce partitioned matching games as a suitable model for international kidney exchange programmes, where in each round the total number of available kidney transplants needs to be distributed amongst the participating countries in a “fair” way. A partitioned matching game (N, v) is defined on a graph$$G=(V,E)$$ $G=(V,E)$with an edge weightingwand a partition$$V=V_1 \cup \dots \cup V_n$$ $V=V_1\cup \cdots \cup V_n$. The player set is$$N = \{ 1, \dots , n\}$$ $N=\{1,\cdots ,n\}$, and player$$p \in N$$ $p\in N$owns the vertices in$$V_p$$ $V_p$. The valuev(S) of a coalition $$S \subseteq N$$ $S\subseteq N$is the maximum weight of a matching in the subgraph ofGinduced by the vertices owned by the players in S. If$$|V_p|=1$$ $|V_p|=1$for all$$p\in N$$ $p\in N$, then we obtain the classical matching game. Let$$c=\max \{|V_p| \; |\; 1\le p\le n\}$$ $c=max\left\{\right|V_p\left|\right|1\le p\le n\}$be the width of (N, v). We prove that checking core non-emptiness is polynomial-time solvable if$$c\le 2$$ $c\le 2$but co--hard if$$c\le 3$$ $c\le 3$. We do this via pinpointing a relationship with the known class ofb-matching games and completing the complexity classification on testing core non-emptiness forb-matching games. With respect to our application, we prove a number of complexity results on choosing, out of possibly many optimal solutions, one that leads to a kidney transplant distribution that is as close as possible to some prescribed fair distribution.